package com.suxin.algorithm.sort;

import java.util.Arrays;

/**
 * @author Tang
 * @classname HeapSort
 * @description [ 堆排序 ]
 * 自下而上建堆
 *
 * @date 2023/1/3 17:27
 */
public class HeapSort {

    private static final int[] DATA = {4,6,1,2,9,8,3,5};

    static void heapSort(int start,int end) {
        // 父节点
        int parent = start;
        // 左右节点最大的节点下标
        int maxIndex,left,right;
        while (parent * 2 + 1 < end) {
            maxIndex = parent * 2 + 1;
            left = parent * 2 + 1;
            right = parent * 2 + 2;
            //  左节点   右节点, 需要防止没有右节点,只有左节点
            if (right < end) {
                if (DATA[left] < DATA[right]) {
                    maxIndex = right;
                }else {
                    maxIndex = left;
                }
            }
            // 父节点已经是最大的了，不需要交换了
            if (DATA[maxIndex] < DATA[parent]) {
                return;
            }
            // 和父节点交换最大值
            if (DATA[parent] < DATA[maxIndex]) {
                int tmp = DATA[parent];
                DATA[parent] = DATA[maxIndex];
                DATA[maxIndex] = tmp;
                // 这个地方要用 交换过后的index继续作为父节点：
                // 因为交换过后，下面的节点可能就会不稳定一定的需要向下堆化
                // 继续向下堆化
                parent = maxIndex;
            }
        }
    }

    public static void main(String[] args) {
        // 1.堆的构建步骤: 找到最后一个节点的父节点，从这个节点开始构造最大堆
        // 直到该节点前面的所有节点都处理完毕

        // 最后一个节点的父节点：array.length / 2 - 1
        for (int i = DATA.length / 2 - 1; i >= 0; i--) {
            // 从后往前建
            heapSort(i, DATA.length);
        }

        System.out.println("大堆：" + Arrays.toString(DATA));

        // 2.排序：将堆顶元素和末尾元素进行互换，然后将剩余n-1个元素重新构建堆
        for (int i = DATA.length - 1; i > 0; i--) {
            int tmp = DATA[i];
            DATA[i] = DATA[0];
            DATA[0] = tmp;
            // 重新构建
            heapSort(0, i);
        }

        System.out.println("sort：" + Arrays.toString(DATA));
    }
}
